/**
例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：
    3
   / \
  9  20
    /  \
   15   7

核心:
- 前序: 根节点
- 中序: 左子树、右子树
- 前序序列[i] = 20，在中序序列中的下标值 = 3
    - 20的左子树序列: [0,1,2] => [9,3,5]
    - 20的右子树序列: [4] => [7]
*/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

class Solution {
private:
    unordered_map<int, int> inorder_value_index_map;

public:
    TreeNode* myBuildTree(
        const vector<int>& preorder, int preorder_left, int preorder_right,
        const vector<int>& inorder, int inorder_left, int inorder_right)
    {
        // 1. 如果 前序节点下标志 > 中序节点下标志，说明 树 已经构建结束
        if (preorder_left > preorder_right) {
            return nullptr;
        }

        // 2. 当前 前序序列中的 起始节点的下标，就是当前构造的子树的 root 节点
        int preorder_root = preorder_left;

        // 3. 找到 当前【前序】节点 preorder[preorder_root]，位于【中序】中的数组下标
        // - inorder_root 根节点
        // - [inorder_left, inorder_root) 左子树节点
        // - (inorder_root, inorder_right) 右子树节点
        int inorder_root = inorder_value_index_map[preorder[preorder_root]];

        // 4. 建立 子树的 root 节点（假设 3）
        TreeNode* root = new TreeNode(preorder[preorder_root]);

        // 5. 得到【左子树】中的 节点的个数
        int size_left_subtree = inorder_root - inorder_left;

        // 6.1 递归地构造【左子树】
        root->left = myBuildTree(
            preorder,
                preorder_left + 1, preorder_left + size_left_subtree,
            inorder,
                inorder_left, inorder_root - 1
        );

        // 6.2 递归地构造【右子树】
        // 左子树 所有的节点，全部位于 中序序列[根节点下标] 的【右侧】
        root->right = myBuildTree(
            preorder,
                preorder_left + size_left_subtree + 1, preorder_right,
            inorder,
                inorder_root + 1, inorder_right
            );

        // 7.
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
    {
        int n = preorder.size();

        /**
         * 中序遍历 inorder = [9,3,15,20,7] 构造哈希映射，帮助我们快速定位根节点
         *
         * - key: 元素值
         * - value: 元素值的【数组下标值】
         *
         * map = {
         *  9: 0,
         *  3: 1,
         *  15: 2,
         *  20: 3,
         *  7: 4
         * }
         */
        for (int i = 0; i < n; ++i) {
            inorder_value_index_map[inorder[i]] = i;
        }

        // 递归 构造树
        return myBuildTree(
            preorder, 0, n - 1,
            inorder, 0, n - 1
        );
    }
};
